package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author Elephas
 * @Date 2022/1/13
 **/
public class CopyRandomList {
    /*
        解法一：利用哈希表，节点和索引一一对应，时间复杂度o(n),空间复杂度o(n)
     */

    public Node copyRandomList(Node head){
        Map<Node,Integer> nodeIntegerMap = new HashMap<>();
        Map<Integer,Node> integerNodeMap = new HashMap<>();
        Map<Node,Integer> newNodeIntegerMap = new HashMap<>();
        Map<Integer,Node> newIntegerNodeMap = new HashMap<>();

        int index = 0;
        Node cur = head;

        // 建立一对一对应关系
        while(cur != null){
            nodeIntegerMap.put(cur,index);
            integerNodeMap.put(index,cur);
            index++;
            cur = cur.next;
        }
        // 初始化新节点map
        index = 0;
        cur = head;
        while(cur != null){
            Node temp = new Node(0);
            temp.val = integerNodeMap.get(index).val;
            newNodeIntegerMap.put(temp,index);
            newIntegerNodeMap.put(index,temp);
            index++;
            cur = cur.next;
        }

        // 复制
        Node next,randomNext,newCur,newNext;
        int nextIndex,randomNextIndex;
        for (int i = 0; i < newIntegerNodeMap.size(); i++) {
            cur = integerNodeMap.get(i);
            next = cur.next;
            if(next != null) {
                nextIndex = nodeIntegerMap.get(next);
                //更新next属性
                newCur = newIntegerNodeMap.get(i);
                newCur.next = newIntegerNodeMap.get(nextIndex);
                randomNext = cur.random;
                //更新random属性
                if(randomNext != null){
                    randomNextIndex = nodeIntegerMap.get(randomNext);
                    newCur.random = newIntegerNodeMap.get(randomNextIndex);
                }else{
                    newCur.random = null;
                }
            }else{
                //next为空也可能有random子项
                newCur = newIntegerNodeMap.get(i);
                newCur.next = null;
                randomNext = cur.random;
                //更新random属性
                if(randomNext != null){
                    randomNextIndex = nodeIntegerMap.get(randomNext);
                    newCur.random = newIntegerNodeMap.get(randomNextIndex);
                }else{
                    newCur.random = null;
                }
            }
        }

        return newIntegerNodeMap.get(0);
    }

}
class NodeWrapper{
    Node innerNode;
    int curIndex;
    int randomIndex;
    NodeWrapper(Node node){
        this.innerNode = node;
    }
}
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
